// 两棵二叉树合并，相同位置如果都有值则相加
// 递归法，先构造节点然后构造左右子树

using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};
// 构造一棵全新的树
TreeNode *merge(TreeNode *root1, TreeNode *root2)
{
    TreeNode *node;
    if (!root1 && !root2)
        return nullptr;
    // 设置节点的值
    else if (!root1 && root2)
        node = new TreeNode(root2->val);
    else if (!root2 && root1)
        node = new TreeNode(root1->val);
    else if (root1 && root2)
        node = new TreeNode(root1->val + root2->val);

    // 构造左右子树
    // 一定要有三种情况，因为如果某一个节点不存在但是要创建，会无法访问不存在的节点，要使用nullptr代替
    if (root1 && root2)
    {
        node->left = merge(root1->left, root2->left);
        node->right = merge(root1->right, root2->right);
    }
    else if (!root1 && root2)
    {
        node->left = merge(nullptr, root2->left);
        node->right = merge(nullptr, root2->right);
    }
    else if (!root2 && root1)
    {
        node->left = merge(root1->left, nullptr);
        node->right = merge(root1->right, nullptr);
    }

    return node;
}

TreeNode *mergeTrees(TreeNode *root1, TreeNode *root2)
{
    if (!root1 && !root2)
        return nullptr;
    return merge(root1, root2);
}


//递归法——原地修改，最后返回某一棵树的根节点
TreeNode* mergeTrees_(TreeNode* root1,TreeNode* root2)
{
    if(!root1) return root2;
    if(!root2) return root1;    
    root1->val+=root2->val;
    root1->left=mergeTrees_(root1->left,root2->left);
    root1->right=mergeTrees_(root1->right,root2->right);

    return root1;
}


//迭代法_使用队列的层序遍历实现
//遍历两棵树，就把两棵树的节点同时出队入队，这样拿到的两个节点就是两棵树的相同位置
//要保证同时出队入队，还有在两个节点都存在才入队。
//原地修改t1，如果t1的节点不存在而t2的存在，之间将其复制过去即可
#include<queue>
using std::queue;
TreeNode* mergeTrees_queue(TreeNode* t1,TreeNode* t2)
{
    if(!t1) return t2;
    if(!t2) return t1;
    queue<TreeNode*> que;
    que.push(t1);
    que.push(t2);
    //注意t1和t2的顺序要固定
    while (!que.empty())
    {
        TreeNode* node1=que.front(); que.pop();
        TreeNode* node2=que.front(); que.pop();
        node1->val+=node2->val; //node1和node2一定存在


        //入队
        if(node1->left&&node2->left){
            que.push(node1->left);
            que.push(node2->left);
        }
        if(node1->right&&node2->right){
            que.push(node1->right);
            que.push(node2->right);
        }


        //将t2的独有节点复制到t1
        if(!node1->left&&node2->left)
            node1->left=node2->left;
        if(!node1->right&&node2->right)
            node1->right=node2->right;
    }
    return t1;
    
}



#include <stack>
using std::stack;
//使用栈的做法
//和队列差不多，需要注意的是入队顺序和入栈顺序不一样，
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
    if(!t1) return t2;
    if(!t2) return t1;
    stack<TreeNode*> st;
    st.push(t1);
    st.push(t2);
    while (!st.empty())
    {
        //node1和node2对于t1，t2，弹出顺序要反过来才能对号入座
        TreeNode* node2=st.top(); st.pop();
        TreeNode* node1=st.top(); st.pop();
        node1->val+=node2->val; //node1和node2一定存在


        //入栈是先右后左
        if(node1->right&&node2->right){
            st.push(node1->right);
            st.push(node2->right);
        }
        if(node1->left&&node2->left){
            st.push(node1->left);
            st.push(node2->left);
        }


        //这里顺序不影响
        //将t2的独有节点复制到t1
        if(!node1->right&&node2->right)
            node1->right=node2->right;
        if(!node1->left&&node2->left)
            node1->left=node2->left;
    }

    return t1;

}